Recommendation systems based on collaborative filtering are a popular and useful way to recommend items and things (e.g., movies, music, products, restaurants, services, websites, etc.) to users. Typically, a user is recommended one or more items based on the items that the user has used and/or rated in view of the items that have been used and/or rated by other users. For example, a user may have provided ratings for a set of movies that the user has viewed. The user may then be recommended other movies to view based on the movies rated by other users who have provided at least some similar ratings of the movies rated by the user. Other examples of collaborative filtering systems may be systems that recommend websites to a user based on the websites that the user has visited, systems that recommend items for purchasing by a user based on items that the user has purchased, and systems that recommend restaurants to a user based on ratings of restaurants that the user has submitted.
While collaborative filtering is useful for making recommendations, there are also privacy concerns associated with collaborative filtering. For example, a user of an online store may not object to the use of their ordering history or ratings to make anonymous recommendations to other users and to themselves, but the user may not want other users to know the particular items that the user purchased or rated.
Previous solutions to this problem have focused on protecting the data that includes the user ratings. For example, user purchase histories may be kept in a secure encrypted database to keep malicious users from obtaining the user purchase histories. However, these systems may be ineffective at protecting the differential privacy of its users. A system is said to provide differential privacy if the presence or absence of a particular record or value cannot be determined based on an output of the system. For example, in the case of a website that allows users to rate movies, a curious user may attempt to make inferences about the movies a particular user has rated by creating multiple accounts, repeatedly changing the movie ratings submitted, and observing the changes to the movies that are recommended by the system. Such a system may not provide differential privacy because the presence or absence of a rating by a user (i.e., a record) may be inferred from the movies that are recommended (i.e., output).